A computer application being executed by a computing device typically provides a page to a device for printing and/or display in the form of a description of the page, with the description provided to device driver software of the device in a page description language (PDL), such as Adobe® PDF or Hewlett-Packard® PCL. The PDL provides descriptions of objects to be rendered onto the page, as opposed to a raster image of the page to be reproduced, for example by printing onto a hard copy medium such as paper, or display upon a video display device. Equivalently, a set of descriptions of graphic objects may be provided in function calls to a graphics interface, such as the Graphical Device Interface (GDI) in the Microsoft Windows™ operating system, or X-11 in the Unix™ operating system, as used in many computing devices. The page is typically rendered for printing and/or display by an object-based graphics system, also known as a Raster Image Processor (RIP).
A PDL-based printer must be able to reliably handle PDL input of high complexity. However it is not always possible to interpret highly complex PDL input in its entirety prior to pixel generation in view of the typically limited memory and processor resources available in a printer system. Consequently, several methods have been utilized to enable PDL printers to process highly complex input PDL jobs prior to final pixel generation.
One of such method involves dividing a complex PDL input into batches of foreground objects which are scan-converted and composited onto a background bitmap. The resultant bitmap may be compressed and be used as the background bitmap for subsequent foreground object batches. The increased processing of compressed bitmaps will impact on the overall performance as each bitmap has to be decompressed before compositing. Furthermore, compression artefacts are also likely to be introduced to the compositing operation, and this will consequently degrade the quality of the final output. Even if a lossless compression technique is used, this method will require a large amount of memory to store the background bitmap. Other similar methods divide the page into strips and batch objects according to these strips, but they suffer the same disadvantages.
Other methods convert a batch of consecutive PDL input objects to an intermediate representation, such as a fillmap. FIG. 1 is a schematic flow diagram that demonstrates the top-level processing of this method. The batch fillmaps are merged into a merged fillmap to reduce memory usage. Due to the lossless and compact nature of fillmaps, the merged fillmap will often lead to a good saving of system resources while preserving the original quality of the PDL data. Thus, this method overcomes performance and quality degradation that is seen in other bitmap based approaches. Although this method works well for many common test cases, resources may still run out during the merging process for some unusual cases. For example, when the number of unique fill compositing sequences generated from overlapping translucent objects in a PDL input exceeds a predetermined threshold associated with available printer system resources, the merging process will run out of resources (typically memory resources) for keeping (storing) the fill compositing sequence after merging. Without a means of recovery, this drawback is catastrophic in a system such as a printer, especially considering that printers do not usually have many system resources available. When resources are exhausted, the printer will have no choice but to halt the printing of the PDL data and possibly leave the user with a printed page with incorrect output.
The disadvantages of such methods include high computational complexity, high memory storage requirements, degraded output quality and a potential out-of-resources condition in unusual cases. Consequently, what is needed is a method for processing input objects using limited resources with efficiency while maximising the quality of the generated pixel output.